package com.zlp.partice;

import org.junit.Test;

import java.util.*;

/**
 * @Author: zhulaiping
 * @Date: 2021/9/1 9:55
 */
public class Day0901 {
    @Test
    public void ee(){
        compareVersion("0.1","1.1");
    }
    public int compareVersion(String v1, String v2) {
        String[] s1 = v1.split("\\.");
        String[] s2 = v2.split("\\.");
        int len = s1.length<s2.length? s1.length:s2.length;
        int i=0;
        for (;i<len;i++){
            int val1 = Integer.valueOf(s1[i]);
            int val2 = Integer.valueOf(s2[i]);
            if(val1<val2) return  -1;
            else if(val1>val2) return  1;
        }
        while (i<s1.length){
            if(Integer.valueOf(s1[i])>0){
                return 1;
            }
            i++;
        }
        while (i<s2.length){
            if(Integer.valueOf(s2[i])>0){
                return -1;
            }
            i++;
        }
        return  0;
    }
    public class ListNode {
        int val;
        ListNode next;
        ListNode(int x) { val = x; }
    }
    public ListNode getKthFromEnd(ListNode head, int k) {
        ListNode fast = head,solw = head;
        while (k-->0) fast = fast.next;
        while (fast!=null){
            fast = fast.next;
            solw = solw.next;
        }
        return solw;
    }

    public int[] smallestK(int[] arr, int k) {
        int[] ret = new int[k];
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        for (int v:arr) queue.add(v);
        int i = 0;
        while (k-->0){
            ret[i++] = queue.poll();
        }
        return ret;
    }
    public int fib(int n) {
        if(n==1||n==2) return 1;
        int[] ret = new int[n];
        ret[0] = 1;
        ret[1] = 1;
        int mod = (int) 1e9;
        for (int i=2;i<n;i++){
            ret[i] = ret[i-1] + ret[i-2];
            ret[i] %= mod;
        }
        return ret[n-1];
    }
    public int search(int[] nums, int target) {
        int l = 0, r = nums.length-1;
        while (l<r){
            int mid = l+(r-l>>1);
            if(nums[mid] == target) return mid;
            if(nums[mid]>target){
                r = mid - 1;
            }else{
                l = mid + 1;
            }
        }
        return -1;
    }
    public int balancedStringSplit(String s) {
        int cnt = 0,ret = 0;
        for (char ch:s.toCharArray()){
            cnt += ch=='R'?-1:1;
            if(cnt==0) ret++;
        }
        return ret;
    }
    @Test
    public void ww(){
        System.out.println();
    }
    public int chalkReplacer(int[] chalk, int k) {
        long sum = 0;
        for (int val:chalk) sum+=val;
        int index = 0;
        k %= sum;
        while (k>=0){
            k -= chalk[index++];
        }
        return index-1;
    }
    public int findPeakElement(int[] nums) {
        int l = 0,r = nums.length-1;
        while (l<=r){
            int mid = l+(r-l>>1);
            if(nums[mid]>nums[mid+1]){
                r = mid-1;
            }else{
                l = mid+1;
            }
        }
        return l;
    }
    public boolean checkValidString(String s) {
        LinkedList<Integer> stack = new LinkedList<>();
        LinkedList<Integer> stack2 = new LinkedList<>();
        char[] chars = s.toCharArray();
        for (int i=0;i<chars.length;i++){
            if(chars[i]=='(') stack.push(i);
            if(chars[i]==')') {
                if(stack.size()>0){
                    stack.pop();
                }else if(stack2.size()>0){
                    stack2.pop();
                }else return false;
            }
            if(chars[i]=='*') stack2.push(i);
        }
        while (stack.size()>0&&stack2.size()>0){
            Integer s1 = stack.pop();
            Integer s2 = stack2.pop();
            if(s1>s2) return false;
        }
        return stack.size()>0?false:true;
    }

    public int numberOfBoomerangs(int[][] points) {
        int n = points.length,ret = 0;
        Map<Integer,Integer> map = new HashMap<>();
        //预处理
        for (int i=0;i<n;i++){
            for (int j=0;j<n;j++){
                if(i!=j){
                    int distance = caluate(points[i],points[j]);
                    map.put(distance,  map.getOrDefault(distance, 0) + 1);
                }
            }
            for (Integer val:map.values()){
                ret += val*(val-1);
            }
            map.clear();
        }
        return ret;
    }

    private int caluate(int[] point1, int[] point2) {
        int x1 = point1[0],y1 = point1[1],x2 = point2[0],y2 = point2[1];
        return (x2-x1)*(x2-x1)+(y2-y1)*(y2-y1);
    }

    public String findLongestWord(String s, List<String> dictionary) {
        Collections.sort(dictionary,((o1, o2) ->
            o1.length()!=o2.length()?o2.length()-o1.length():o1.compareTo(o2)
        ));
        System.out.println(dictionary);
        for (String cur:dictionary){
            int j = 0;
            for (int i=0;i<s.length();i++){
                if(s.charAt(i)==cur.charAt(j)){
                    j++;
                    if(j==cur.length()) return cur;
                }
            }
        }
        return "";
    }

    public boolean isValidSudoku(char[][] board) {
        boolean[][] c = new boolean[9][9];
        boolean[][] r = new boolean[9][9];
        boolean[][] z = new boolean[9][9];
        for (int i=0;i<9;i++){
            for (int j=0;j<9;j++){
                if(board[i][j]=='.') continue;
                int val = board[i][j] - '0';
                //计算属于哪个方格
                int k = i/3*3 + j/3;
                if(c[i][val-1]||r[j][val-1]||z[k][val-1]) return false;
                else{
                    c[i][val-1] = true;
                    r[j][val-1] = true;
                    z[k][val-1] = true;
                }
            }
        }
        return true;
    }

    class Trie{
        LinkedList<Character> r;
        int isLesf;//0：普通节点，1：叶子节点
        Trie chlidren;
        public Trie(){
            r = new LinkedList<>();
        }
    }
    @Test
    public void qee(){
       findWords(null,new String[]{"oath","pea","eat","rain"});
    }

    public List<String> findWords(char[][] board, String[] words) {

        return null;
    }
    public int minSteps(int n) {
        int ret = 0;
        for (int i=2;i<=n;i++){
            while (n%i==0){
                ret += i;
                n /= i;
            }
        }
        return ret;
    }

    public int lengthOfLastWord(String s) {
        int ret = 0;
        boolean flag = false;
        char[] arr = s.toCharArray();
        for (int i=arr.length-1;i>=0;i--){
            if(arr[i]==' '&&!flag) continue;
            if(arr[i]!=' '){
                ret++;
                flag = true;
            }
        }
        return ret;
    }
    public ListNode[] splitListToParts(ListNode head, int k) {
        ListNode[] ret = new ListNode[k];
        List<ListNode> temp = new ArrayList<>();
        while (head!=null){
            temp.add(head);
            head = head.next;
        }
        int m = temp.size()%k,n = temp.size()/k;
        int cur = 0;
        for (int i=0;i<k&&cur<temp.size();i++){

            ret[i] = temp.get(cur);
            if(m>0){
               cur += n+1;
               m--;
            }else cur += n;
            temp.get(cur-1).next = null;
        }
         return ret;
    }
    public boolean isPowerOfThree(int n) {
        if(n<3) return false;
        while (n!=1){
            if(n%3!=0) return false;
            n /= 3;
        }
        return true;
    }

}
